/*
 * @lc app=leetcode.cn id=77 lang=swift
 *
 * [77] 组合
 */

// @lc code=start
class Solution77 {
    var result: [[Int]] = []
    var path: [Int] = []
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        backTrace(n: n, k: k, start: 1)
        return result
    }
    func backTrace(n: Int, k: Int, start: Int) {
        if path.count == k {
            result.append(path)
            return
        }
        if start > n {
            return
        }
        // right 当剩下的数不足以组成组合时可以提前退出（剪枝）
        let right = n - (k - path.count) + 1
        for i in start...right {
            path.append(i)
            backTrace(n: n, k: k, start: i + 1)
            path.removeLast()
        }
    }
    static func test() {
        let solution = Solution77()
        let result = solution.combine(1, 1)
        print(result)
    }
}
// @lc code=end

